As machine-based character recognition has become increasingly desirable, a number of systems capable of recognizing handwritten (unconstrained) text have been proposed. These systems typically divide the problem of character recognition into two interrelated tasks: (1) segmenting the text into individual character patterns (performed by the system's "segmentor"); and (2) classifying each character pattern into its alphabetic or numeric value (performed by the system's "classifier"). In any practical character recognition system both of these tasks must be performed efficiently and accurately.
The complexity of these tasks is exacerbated in the context of recognition systems capable of recognizing handwritten text in that each instance of a particular handwritten character inevitably varies slightly, even when written by the same person. This requires that the character recognition system exhibit considerable flexibility in classifying each character. Moreover, it is frequently desirable to recognize handwritten text interactively as it is drawn. This allows the writer to quickly adjust for mistakes in writing and/or misinterpretations by the character recognition system. It is additionally desirable for the electronic pen to respond quickly and smoothly to permit the author to draw smooth continuous lines without hesitation.
Presently known approaches to recognizing handwritten text are encumbered by a trade-off between the complexity of the segmentation task and that of the classification task: since both character segmentation and classification are computationally expensive, the computational requirements and time complexity of each task must be critically evaluated in order to achieve optimal system performance. This is true for several reasons. First, accurate character segmentation reduces the amount and complexity of the character pattern data which must be communicated from the segmentor to the classifier.
Moreover, the accuracy of the character classification task directly depends on the quality of the character pattern data which is transmitted from the segmentor to the classifier. If the character patterns are clear and unambiguous, the classification task is substantially eased. Conversely, the classification task becomes progressively more difficult as the integrity of the character pattern data transmitted from the segmentor to the classifier decreases.
Existing recognition systems typically employ some form of segmentation to initially separate individual character patterns from input image data. Some approaches simply apply a fixed intensity threshold to the sampled image data, effectively converting the input image into a two-dimensional array, called a "bitmap", comprising, for example, black pixels for the character patterns and white pixels for the background. See, for example, U.S. Pat. No. 4,903,303 to Tachikawa and U.S. Pat. No. 4,162,482 to Su.
Similarly, in U.S. Pat. No. 4,606,069 to Johnsen, a technique and apparatus for facsimile encoding employs a pattern extractor to effectively segment graphic elements, such as line segments and black regions, for subsequent matching. The pattern extractor includes a pattern isolator which isolates symbolic and non-symbolic patterns, and a feature extractor which extracts preselected feature patterns for comparison with stored pattern features. Once an individual character (e.g. an alphanumeric "B", "8", or the like) is segmented, the corresponding character pattern data is sent to a classifier for identification of that character.
U.S. Pat. No. 4,700,400 to Ross presents a concise review of character classification methods, wherein the various methods are divided into two categories: "matching" and "feature analysis". In matching methods, each input character is compared on a pixel-by-pixel basis with one or more known character patterns stored in memory. The degree of correlation is ascertained and the stored character having the highest correlation is selected as the match for that input character. In feature analysis, rather than comparing entire character patterns, indicia of specific features (e.g. slope, curvature, line intersections, etc.) are first extracted from the character data and then compared with corresponding indicia of known features of one or more stored characters. Again, the character having the highest degree of correlation is selected as the match for that input character.
Regardless of the particular segmentation scheme employed, presently known character recognition systems typically process the entire bitmap during the segmentation process. Consequently, characters represented in the bitmap which have already been segmented are reprocessed, resulting in unnecessary computational complexity. Moreover, processing the entire bitmap necessarily involves processing irrelevant non-character data such as background and transmission noise.
A need exists for a segmentation method and apparatus which can segment handwritten characters interactively as they are written, thereby allowing the user to continue entering data during the segmentation process.